INCLUDE Irvine32.inc

.data
arr DWORD 3h,-1h,8h,1h,9h,0h,4h,5h			;new Array{3,-1,8,1,9,0,4,5}
l DWORD 0h	
h DWORD 7h
i DWORD ?
j DWORD ?
w DWORD ?
space byte " ",0
stackEnd DWORD ?
stackStart DWORD ?

.code
main:
mov eax,0h
mov l,eax	
mov eax,7h
mov h,eax	
mov esi,OFFSET stackStart
mov stackEnd,esi

quicksort:
	mov eax,l
	mov ebx,h
	cmp eax,ebx	;if low<high
	jge quickEnd ;low>=high, jump
	jmp partition ;execute partition

	pushStack:
		mov w,eax ;eax has the return value of partition
		mov eax,l
		mov ebx,stackEnd ;end of stack
		mov [ebx],eax ;push low into stack
		add stackEnd,4h 
		
		mov eax,w
		mov ebx,stackEnd ;end of stack
		mov [ebx],eax ;push w into stack
		add stackEnd,4h 
		
		mov eax,w
		inc eax
		mov ebx,stackEnd ;end of stack
		mov [ebx],eax ;push w into stack again
		add stackEnd,4h 
		
		mov eax,h
		mov ebx,stackEnd
		mov [ebx],eax ;push high into stack
		add stackEnd,4h
	
	quickEnd:
		;test whether the stack is empty
		mov esi,OFFSET stackStart
		mov ecx,stackEnd
		cmp esi,ecx
		je quickOver ;the sorting is over
		
		sub stackEnd,4h ;pop the stack
		mov ebx,stackEnd ;end of stack
		mov eax,[ebx]
		mov h,eax
		sub stackEnd,4h ;pop the stack
		mov ebx,stackEnd ;end of stack
		mov eax,[ebx]
		mov l,eax
		jmp quicksort ;the recursion

partition:
	;parameter: l and h. partition on arr
	mov esi,OFFSET arr
	mov eax,l
	mov i,eax ;i=low
	mov ebx,h
	mov j,ebx ;j=high
	
	loopStart:
		mov eax,i
		mov ebx,j
		cmp eax,ebx
		jge return ;i>=j, return
		
		innerLoopA:
			mov eax,i
			mov ebx,j
			cmp eax,ebx
			jge outsideInnerLoopA
			mov ecx,[esi+4*eax] ;ecx=arr[low]
			mov edx,[esi+4*ebx] ;edx=arr[high]
			cmp ecx,edx
			jg outsideInnerLoopA ;if arr[low]>arr[high] jump out
			dec ebx
			mov j,ebx ;high--
			jmp innerLoopA
			
		outsideInnerLoopA:
			mov eax,i
			mov ebx,j
			mov ecx,[esi+4*eax] ;ecx=arr[low]
			mov edx,[esi+4*ebx] ;edx=arr[high]
			mov [esi+4*eax],edx
			mov [esi+4*ebx],ecx
		
		innerLoopB:
			mov eax,i
			mov ebx,j
			cmp eax,ebx
			jge outsideInnerLoopB
			mov ecx,[esi+4*eax] ;ecx=arr[low]
			mov edx,[esi+4*ebx] ;edx=arr[high]
			cmp ecx,edx
			jg outsideInnerLoopB ;if arr[low]>arr[high] jump out
			inc eax
			mov i,eax ;low++
			jmp innerLoopB
			
		outsideInnerLoopB:
			mov eax,i
			mov ebx,j
			mov ecx,[esi+4*eax] ;ecx=arr[low]
			mov edx,[esi+4*ebx] ;edx=arr[high]
			mov [esi+4*eax],edx
			mov [esi+4*ebx],ecx
			
		jmp loopStart ;return to the begin of the loop
		
	return:
		mov eax,i ;eax is the return value
		jmp pushStack;
		
quickOver:
	mov esi,OFFSET arr
	mov eax,[esi]
	call WriteInt
	mov edx,OFFSET space
	call WriteString
	add esi,4h
	mov eax,[esi]
	call WriteInt
	mov edx,OFFSET space
	call WriteString
	add esi,4h
	mov eax,[esi]
	call WriteInt
	mov edx,OFFSET space
	call WriteString
	add esi,4h
	mov eax,[esi]
	call WriteInt
	mov edx,OFFSET space
	call WriteString
	add esi,4h
	mov eax,[esi]
	call WriteInt
	mov edx,OFFSET space
	call WriteString
	add esi,4h
	mov eax,[esi]
	call WriteInt
	mov edx,OFFSET space
	call WriteString
	add esi,4h
	mov eax,[esi]
	call WriteInt
	mov edx,OFFSET space
	call WriteString
	add esi,4h
	mov eax,[esi]
	call WriteInt
exit
END main